%%%-------------------------------------------------------------------
%%% File    : p29.erl
%%% Author  :  Plamen Dragozov <plamen at dragozov.com>
%%% Description : 
%%% Consider all integer combinations of a^(b) for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
%%%
%%%     2^(2)=4, 2^(3)=8, 2^(4)=16, 2^(5)=32
%%%     3^(2)=9, 3^(3)=27, 3^(4)=81, 3^(5)=243
%%%     4^(2)=16, 4^(3)=64, 4^(4)=256, 4^(5)=1024
%%%     5^(2)=25, 5^(3)=125, 5^(4)=625, 5^(5)=3125
%%%
%%% If they are then placed in numerical order, with any 
%%% repeats removed, we get the following sequence of 15 distinct terms:
%%%
%%% 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
%%%
%%% How many distinct terms are in the sequence generated 
%%% by a^(b) for 2 < a < 100 and 2 < b < 100?
%%%
%%% Created : 23 Dec 2008
%%%-------------------------------------------------------------------
-module(p29).

%% API
-compile(export_all).

%%====================================================================
%% API
%%====================================================================
%%--------------------------------------------------------------------
%% Function: 
%% Description:
%%--------------------------------------------------------------------
solution(N)->
    count(2, N+1, 2, N+1, ets:new(lookup, [])). 

%%====================================================================
%% Internal functions
%%====================================================================

count(MaxA, MaxA, _, _, Tbl) ->
    ets:info(Tbl, size);
count(A, MaxA, MaxB, MaxB, Tbl) ->
    count(A+1, MaxA, 2, MaxB, Tbl);
count(A, MaxA, B, MaxB, Tbl) ->
    ets:insert(Tbl, {power_key(A, B), 1}),
    count(A, MaxA, B+1, MaxB, Tbl).

%a = (2**p2)*(3**p3)*..*(n**pn), where 2, 3, ..., n are the prime factors of a
%a**b = (2**(p1*b))*(3**(p3*b))*...*(n**(pn*b))
power_key(A, B) ->
    power_key(A, 2, 0, B, <<>>).

power_key(N, I, Counter, B, Bin) when I > (N div 2)->
    case true of
        true when I =:= N -> <<((Counter + 1)*B):32/integer, N:32/integer, Bin/binary>>;
        true when Counter > 0 -> <<B:32/integer, N:32/integer, (B*Counter):32/integer, I:32/integer, Bin/binary>>;
        _ -> <<B:32/integer, N:32/integer, Bin/binary>>
    end;
power_key(N, I, Counter, B, Bin) ->
    case true of
        true when (N rem I) =:= 0 ->
            power_key(N div I, I, Counter + 1, B, Bin);
        true when Counter > 0 ->
            power_key(N, I + 1, 0, B, <<(B*Counter):32/integer, I:32/integer, Bin/binary>>);
        _ ->
            power_key(N, I + 1, 0, B, Bin)
    end.

